Problém obchodného cestujúceho

Problém obchodného cestujúceho (z angl. travelling salesman problem - skratka TSP) je jedna z najznámejších optimalizačných úloh. Je to aj vďaka veľkému množstvu jej praktických aplikácií (rozvoz tovaru, osadzovanie súčiastok plošného spoja a podobne).

Podstata problému

Nech je daných N miest a nech je možné dostať sa z každého mesta do všetkých ostatných (buď priamo alebo cez niektoré iné mesto). Nech je každá cesta medzi dvomi navzájom prepojenými mestami ohodnotená číslom, ktoré môže vyjadrovať vzdialenosť, cenu, čas atď. Cieľom obchodného cestujúceho je vybrať sa z mesta, v ktorom sa práve nachádza, navštíviť každé mesto práve raz a vrátiť sa do počiatočného mesta. Pritom sa snaží túto cestu absolvovať tak, aby precestoval čo najmenšiu vzdialenosť, zaplatil čo najmenej peňazí a podobne.

Dejiny

Problém obchodného cestujúceho sa datuje od 19. storočia. V tom období sa ním zaoberal írsky matematik Sir William Rowan Hamilton a britský matematik Thomas Kirkman. V tridsiatych rokoch 20. storočia bola na univerzite vo Viedni a Harvarde popísaná presnejšia matematická formulácia. Výskumné tímy Grotschela a Padberga v priebehu jedného roka (1987) vyriešili úlohy s 532 mestami v USA, so 666 rôznymi miestami na svete a úlohy vŕtania otvorov pri výrobe dosiek s tlačenými spojmi s 1002 a 2392 bodmi.

Applegate, Bixby, Chvátal a Cook našli v roku 1992 optimálnu cestu pre 3038 miest, na ktorú použili veľkú sieť z paralelne pracujúcich počítačov. V ďalších rokoch postupne zdokonaľovali objavené techniky až v roku 1998 našli optimálnu cestu medzi 13509 mestami v USA, v roku 2004 optimálnu cestu medzi 24978 mestami vo Švédsku a nakoniec v roku 2006 cestu medzi 85900 bodov. Pri riešení týchto úloh používali softvér Concorde, ktorý je k dispozícii na internete.

Problém obchodného cestujúceho v teórii grafov

V terminológii teórie grafov jednotlivé mestá predstavujú vrcholy, prepojenia medzi mestami sú hrany. Ide o hranovo ohodnotený súvislý graf G=(V, H), v ktorom hľadáme hamiltonovskú kružnicu, ktorá má minimálny súčet ohodnotení hrán.

Základné definície a pojmy:

Hamiltonovská kružnica je taký podgraf, ktorý je kružnica a obsahuje všetky vrcholy pôvodného grafu.

Graf G, ktorý má aspoň jednu hamiltonovskú kružnicu, nazývame hamiltonovským grafom.

Nech pre ľubovoľné dva nesusedné vrcholy u, v grafu G=(V, H), |V| = n, n ≥ 3, platí: $\delta (u)+\delta (v)\geq n$, potom G je hamiltonovský graf.

Nech G=(V, H), |V| = n, n ≥ 3. Nech pre každé celé číslo j, $1\leq j\leq {\frac {n}{2}}$, počet vrcholov stupňa najviac j je menší než j, potom graf G obsahuje hamiltonovskú kružnicu.

Pre kompletný graf K_n, kde n ≥ 3, počet všetkých rôznych hamiltonovských kružníc vieme určiť podľa nasledujúceho vzťahu: ${\frac {1}{2}}(n-1)!$

Riešenie problému

Problém obchodného cestujúceho je klasifikovaný ako tzv. NP-úplný. To znamená, že so vzrastajúcim počtom miest rastie čas riešenia exponenciálne. Napríklad, ak vezmeme kompletný graf, tak pri návšteve 4 miest máme tri potenciálne cesty. Návšteva 12 miest bude znamenať už takmer 20 miliónov možností. Pri 16 mestách sa číslo šplhá až na neuveriteľných viac ako 653 biliónov potenciálnych ciest. Zatiaľ však nie je známy žiaden efektívny algoritmus, ktorý by v polynomiálnom čase rozhodol o riešení.

K problému môžeme pristupovať tromi základnými spôsobmi:

• algoritmy pre presné nájdenie riešenia (pre problémy s malým počtom vrcholov)
• suboptimálne a heuristické algoritmy (osvedčené v dostatočnom počte prípadov, nedokázateľné, nemusia zaručovať optimálne riešenia ani hromadnosť)
• nájdenie špeciálneho prípadu, pre ktorý vieme určiť presné riešenie

Sú známe niektoré možnosti riešenia z rôznych oblastí:

• Umelá inteligencia:
  1. neurónové siete:
     • Hopfieldova sieť
  2. prírodne inšpirované prehľadávacie algoritmy:
     • umelé mravce
     • evolučné, genetické algoritmy
     • simulované žíhanie
• Znalostné systémy:
  1. rozhodovacie stromy

Príklad

Máme riešiť problém obchodného cestujúceho, ktorého graf je na nasledujúcom obrázku:

Pre nájdenie riešenia použijeme rozhodovací strom. Obchodný cestujúci vychádza z mesta A a môže ísť buď do mesta B alebo C. Ak sa rozhodne pre B, opäť má možnosť vybrať si mesto D alebo G. Tento postup opakujeme a vytvárame z týchto výberov ciest rozhodovací strom, kde mesto A predstavuje koreňový uzol. Rozhodovací strom bude mať takúto podobu:

• V prípade, že začíname riešiť graf vo vrchole so stupňom dva, stačí riešiť iba ľavú / pravú stranu rozhodovacím algoritmom, nakoľko je ľavá a pravá strana vzájomne zrkadlená (cesty majú rovnaké ohodnotenie).

Z rozhodovacieho stromu zistíme, že v grafe existuje 6 hamiltonovských kružníc:

• ABDGHFECA (1)
• ABGHEFDCA (2)
• ABGDFHECA (3)
• ACEHFDGBA (4)
• ACEFHGDBA (5)
• ACDFEHGBA (6)

Hamiltonovské kružnice (1) a (5), (2) a (6), (3) a (4) sú rovnaké, líšia sa len smerom „obehu“. Preto ďalej uvažujeme len kružnice (1), (2) a (3). Vypočítame súčty ohodnotení hrán:

• (1) – 18
• (2) – 24
• (3) – 23

Snahou obchodného cestujúceho je cestovať tak, aby prešiel najmenšiu vzdialenosť. Preto riešením tejto úlohy sú hamiltonovské kružnice (1) a (5) so súčtom ohodnotení hrán 18.

Využitie

Problém obchodného cestujúceho má množstvo praktických aplikácií. Využíva sa pri plánovaní dopravy, v prevádzkach, pri umiestňovaní zariadení, plánovaní výroby a riadení dodávateľského reťazca. Napríklad, môže pomôcť znížiť výrobné náklady, ak sa stanoví najefektívnejší model pre dierovanie otvorov do dosky plošných spojov alebo iných predmetov. Otvory, ktoré je potrebné vyvŕtať predstavujú počet miest a čas potrebný k posunu vŕtacej hlavy od jednej diery k nasledujúcej predstavuje cestovné náklady.

Záver

Hoci je problém obchodného cestujúceho známy už pomerne dlho, ešte stále nebol nájdený efektívny algoritmus. Dokonca väčšina odborníkov sa domnieva, že ho nebude možné nikdy riešiť polynomiálnymi algoritmami kvôli jeho zložitosti.

Zdroje

• http://gtresearchnews.gatech.edu/reshor/rh-f04/tsp.html
• http://www.tsp.gatech.edu/index.html Archivované 2008-12-26 na Wayback Machine
• BUČKO, M., KLEŠČ, M.: Diskrétna matematika. 1. vyd. Košice: elfa, 1991. ISBN 80-88786-55-X.
• COOK, W.J.: 2012. Po stopách obchodního cestujícího. Praha: Dokořán, 2012. 256 s. ISBN 978-80-7363-412-4